/**
 * https://leetcode.cn/submissions/detail/583925352/
 * 909. 蛇梯棋
 * Medium, 黄伟杰 2024.11.29
 * BFS
 */

class Solution
{
    pair<int, int> id2(int id, int n)
    {
        int r = (id - 1) / n, c = (id - 1) % n; // r 行，c列
        if (r % 2 == 1)
            c = n - 1 - c;
        return {n - 1 - r, c};
    }

public:
    int snakesAndLadders(vector<vector<int>> &board)
    {
        int n = board.size();
        vector<bool> vis(n * n + 1, false); // 判断是否走过
        queue<pair<int, int>> q;            // pair<id,步数>
        q.emplace(1, 0);                    // 起点
        while (!q.empty())
        {
            auto p = q.front();
            q.pop();
            for (int i = 1; i <= 6; i++) // 最多只能走6步
            {
                int nxt = p.first + i; // 走i
                if (nxt > n * n)       // 超过id
                    break;
                auto rc = id2(nxt, n);
                if (board[rc.first][rc.second] > 0)
                    nxt = board[rc.first][rc.second];
                if (nxt == n * n)
                    return p.second + 1; // 这次的移动没有加入
                if (!vis[nxt])           // 走没走过的地方
                {
                    vis[nxt] = true;
                    q.emplace(nxt, p.second + 1); // 步数+1
                }
            }
        }
        return -1;
    }
};